#include <iostream>
#include <vector>
using namespace std;

/**
 * @brief
 * problem:
 *  Given an integer n, return an array ans of length n + 1
 * such that for each i (0 <= i <= n),
 *  ans[i] is the number of 1's in the binary representation of i.
 * 0 <= n <= 105
 * It is very easy to come up with a solution with a runtime of O(n log n).
 * Can you do it in linear time O(n) and possibly in a single pass?
 * Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
 */
class Solution
{
public:
    /**
     * @brief O(NlogN)
     *
     * @param n
     * @return vector<int>
     */
    vector<int> countBits(int n)
    {
        vector<int> res;
        for (int i = 0; i < n + 1; i++)
        {
            int tmp = i, count = 0;
            while (tmp)
            {
                tmp &= tmp - 1;
                count++;
            }
            res.push_back(count);
        }
        return res;
    }

    vector<int> countBits_2(int n)
    {
        vector<int> ret(n + 1, 0);

        for (int i = 1, prev = 0; i <= n; ++i)
        {
            prev = i & (i - 1);
            ret[i] = 1 + ret[prev];
        }

        return ret;
    }

    vector<int> countBits_3(int n)
    {
        vector<int> dp(n + 1, 0);
        if (n == 0)
        {
            return {0};
        }
        if (n == 1)
        {
            return {0, 1};
        }
        if (n == 2)
        {
            return {0, 1, 1};
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {

            dp[i] = i % 2 ? (dp[i >> 1] + 1) : dp[i >> 1];
        }
        return dp;
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    vector<int> res = s.countBits_3(10);
    for (int r : res)
    {
        cout << r << " ";
    }
    cout << endl;
    return 0;
}
